L'algorithme patience sorting consiste à parcourir séquentiellement les valeurs de permutation dans l'ordre et à les empiler dans un tableau linéaire selon les règles suivantes :
toute nouvelle valeur \(x\) va être remplacée an haut d'une colonne existante, ou va former une nouvelle colonne à droite des colonnes existantes
la colonne sur laquelle une nouvelle valeur \(x\) est placée est la colonne la plus à gauche dont la première valeur est plus grande que \(x\). S'il n'y a pas de telle colonne, alors \(x\) va former une nouvelle colonne
Algorithme patience sorting appliqué à la permutation \((4,1,2,7,6,5,8,9,3)\) :
Propriétés
Lien avec les sous-suites croissantes
Lemme :
Quand on applique l'algorithme patience sorting à une permutation \(\sigma\in\mathfrak S_n\), alors le nombre de colonnes du tableau résultant est égal à la taille de la plus grande sous-suite croissante de \(\sigma\)